#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

#include<vector>

using namespace std;
//打家劫舍II  多状态dp问题
//第一个关键在思路，首先关键在于第一个拿不拿，根据这个划分成两个打家劫舍I的单项问题

//第二个关键在于处理边界问题，主要是在映射关系上不要搞混

//最后一个就是，越界问题，一定要单独并且好好处理，最让我疑惑的是输入三个数的情况，但是用这样单独处理的方式也可以过
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        if (n == 3) return max(nums[0], max(nums[1], nums[2]));
        vector<int> f1(n - 3);
        auto g1 = f1;

        vector<int> f2(n - 1);
        auto g2 = f2;

        f1[0] = nums[2];
        f2[0] = nums[1];

        for (int i = 1; i < n - 3; i++)
        {
            f1[i] = g1[i - 1] + nums[i + 2];
            g1[i] = max(f1[i - 1], g1[i - 1]);

        }

        for (int j = 1; j < n - 1; j++)
        {
            f2[j] = g2[j - 1] + nums[j + 1];
            g2[j] = max(f2[j - 1], g2[j - 1]);
        }
        int ret1 = max(f1[n - 4], g1[n - 4]) + nums[0];
        int ret2 = max(f2[n - 2], g2[n - 2]);

        return max(ret1, ret2);

    }
};


int main()
{



	return 0;
}